﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//给你一个有序数组 nums ，
//请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

// 双指针
class Solution
{
public:
    int removeDuplicates(vector<int>& nums)
    {
        int n = nums.size();
        int left = 2, right = 2;
        if (n <= 2) return n;
        while (right < n)
        {
            // 当 nums[right] == nums[left-1]时
            // nums[left-2] == nums[left-1] == nums[fast]此时不保留
            if (nums[right] == nums[left - 2])
                right++;
            else nums[left++] = nums[right++];
        }

        return left;
    }
};

// 采用计数的方式
class Solution
{
public:
    int removeDuplicates(vector<int>& nums)
    {
        int n = nums.size();
        int count = 1, ret = 1;
        for (int i = 1; i < n; i++)
        {
            if (nums[i] == nums[i - 1])
            {
                count++;
                if (count <= 2)
                {
                    nums[ret++] = nums[i];
                }
            }
            else
            {
                count = 1;
                nums[ret++] = nums[i];
            }
        }

        return ret;
    }
};

//给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n / 2 ⌋ 的元素。
//
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。

// 抵消法
class Solution
{
public:
    int majorityElement(vector<int>& nums)
    {
        // 默认第一个为最多的字符
        int count = 1, tmp = nums[0];
        for (int i = 1; i < nums.size(); i++)
        {
            //与保存的字符相同则计数+1
            if (nums[i] == tmp)
                count++;
            //与保存的字符不同则计数-1
            else count--;
            //计数为0表示有可能保存的字符不是最多的字符，换下一个
            if (count == 0) tmp = nums[i + 1];
        }

        return tmp;
    }
};

// 排序即可，返回中间值
class Solution
{
public:
    int majorityElement(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

//给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
//
//题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> ret(n);
        vector<int> f(n);
        vector<int> g(n);
        f[0] = 1, g[n - 1] = 1;
        // 以i位置为结尾,数组中之前的乘积
        for (size_t i = 1; i < n; i++)
            f[i] = f[i - 1] * nums[i - 1];
        // 以i位置为开头，数组之后的乘积
        for (int i = n - 2; i >= 0; i--)
            g[i] = g[i + 1] * nums[i + 1];
        for (int i = 0; i < n; i++)
            ret[i] = f[i] * g[i];


        return ret;
    }
};

//n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
//
//你需要按照以下要求，给这些孩子分发糖果：
//
//每个孩子至少分配到 1 个糖果。
//相邻两个孩子评分更高的孩子会获得更多的糖果。
//请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
class Solution
{
public:
    int candy(vector<int>& ratings)
    {
        int n = ratings.size();
        vector<int> left(n);
        for (int i = 0; i < n; i++)
        {
            if (i > 0 && ratings[i] > ratings[i - 1])
            {
                left[i] = left[i - 1] + 1;
            }
            else
            {
                left[i] = 1;
            }
        }
        vector<int> right(n);
        for (int i = n - 1; i >= 0; i--)
        {
            if (i<n - 1 && ratings[i] > ratings[i + 1])
            {
                right[i] = right[i + 1] + 1;
            }
            else right[i] = 1;
        }
        int ret = 0;
        for (int i = 0; i < n; i++)
        {
            ret += max(left[i], right[i]);
        }

        return ret;
    }
};

//给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
class Solution
{
public:
    int lengthOfLastWord(string s)
    {
        // 过滤最后面的空格
        int end = s.size() - 1;
        int count = 0;
        while (s[end] == ' ' && end >= 0) end--;
        while (end >= 0 && s[end] != ' ')
        {
            end--;
            count++;
        }
        return count;
    }
};

//编写一个函数来查找字符串数组中的最长公共前缀。
//
//如果不存在公共前缀，返回空字符串 ""。
class Solution
{
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        for (int i = 0; i < strs[0].size(); i++)
        {
            // 统⼀⽐较
            char tmp = strs[0][i];
            for (int j = 1; j < strs.size(); j++)
            {
                if (j == strs.size() || tmp != strs[j][i])
                    return strs[0].substr(0, i);
            }
        }

        return strs[0];
    }
};
int main()
{

	return 0;
}

